#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(9, n, k, res, path);
        return res;
    }

private:
    void dfs(int i, int t, int k, vector<vector<int>>& res, vector<int>& path) {
        int d = k - path.size();  // 还要选 d 个数
        if (t < 0 ||
            t > (i * 2 - d + 1) * d / 2) {  // 剪枝(t 太小 或 大于预估最大和)
            return;
        }
        if (d == 0) {  // 找到一个合法组合
            res.emplace_back(path);
            return;
        }
        for (int j = i; j >= d; j--) {
            path.push_back(j);                // 选 j
            dfs(j - 1, t - j, k, res, path);  // 继续选
            path.pop_back();                  // 恢复现场
        }
    }
};

int main() {
    Solution s;

    vector<vector<int>> res1{{4, 2, 1}};
    vector<vector<int>> res2{{6, 2, 1}, {5, 3, 1}, {4, 3, 2}};
    vector<vector<int>> res3{};

    assert(s.combinationSum3(3, 7) == res1);
    assert(s.combinationSum3(3, 9) == res2);
    assert(s.combinationSum3(4, 1) == res3);

    return 0;
}